Routing devices within a network, often referred to as routers, maintain tables of routing information that describe available routes through the network. Network routers maintain routing information that describes available routes through the network. Upon receiving a packet, a router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more routing protocols, such as an interior gateway protocol (IGP) or Border Gateway Protocol (BGP).
The term “link” is often used to refer to the connection between two devices on a network. The link may be a physical connection such as a copper wire, a coaxial cable, any of a host of different fiber optic lines or a wireless connection. In addition, network devices may define “virtual” or “logical” links, and map the virtual links to the physical links. In other words, the use of virtual links provides a degree of abstraction. As networks grow in size and complexity, the traffic on any given link may approach a maximum bandwidth capacity for the link, thereby leading to congestion and loss.
Multi-protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. Using MPLS, a source device can request a path through a network, i.e., a Label Switched Path (LSP). An LSP defines a distinct path through the network to carry packets from the source device to a destination device. A short label associated with a particular LSP is affixed to packets that travel through the network via the LSP. Routers along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path. LSPs may be used for a variety of traffic engineering purposes including bandwidth management and quality of service (QoS).
Traffic engineering may be applied within a network for a variety of purposes, such as to route traffic around network failures or congested links or to direct certain traffic along a particular path through the network that meets a set of explicit requirements. Historically, MPLS label distribution was driven by protocols such as label distribution protocol (LDP), Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE) and labeled Border Gateway Protocol (LBGP). Procedures for LDP by which label switching routers (LSRs) distribute labels to support MPLS forwarding along normally routed paths are described in L. Anderson, “LDP Specification,” RFC 3036, Internet Engineering Task Force (IETF), January 2001, the entire contents of which are incorporated by reference herein. RSVP-TE uses constraint information, such as bandwidth availability, to compute and establish LSPs within a resource-constrained network. RSVP-TE may use bandwidth availability information accumulated by a link-state interior routing protocol, such as the Intermediate System-Intermediate System (IS-IS) protocol or the Open Shortest Path First (OSPF) protocol, extended to carry traffic engineering information.
Head-end routers of an LSP are commonly known as ingress routers, while routers at the tail-end of the LSP are commonly known as egress routers. Ingress and egress routers, as well as intermediate routers along the LSP that support MPLS, are referred to generically as label switching routers (LSRs). A set of packets to be forwarded along the LSP is referred to as a forwarding equivalence class (FEC). A plurality of FECs may exist for each LSP, but there may be only one active LSP for any given FEC. A FEC definition typically includes the IP address of the destination of the packets traversing the LSP, e.g., an IP address to which the packets are destined. The ingress label edge router (LER) uses routing information, propagated upward along the LSP from the egress LER, to determine the LSP and to affix a label to each packet of the FEC. The LSRs use MPLS protocols to receive MPLS label mappings from downstream LSRs and to advertise MPLS label mappings to upstream LSRs. When an LSR receives an MPLS packet from an upstream router, it switches the MPLS label according to the information in its forwarding table and forwards the packet to the appropriate downstream LSR or LER. The egress LER removes the label from the packet and forwards the packet to its destination in accordance with non-label based packet forwarding techniques.
In general, each router along the LSP maintains a label mapping that associates a FEC with an incoming label and an outgoing label. In this manner, when an LSR receives a labeled packet, the LSR may swap the label (i.e., the incoming label) on the packet with the outgoing label by performing a lookup in the context. The LSR may then forward the packet to the next LSR or LER along the LSP. The next router along the LSP from a given router is commonly referred to as a downstream router or a next hop.
In other words, once a packet is mapped on to an LSP by an LER, the LSRs along the LSP forward the packet based on labels attached to the packet rather than making independent forwarding decisions based on the packet destination and the LSRs' routing information. A Traffic Engineering MPLS LSP (TE LSP) may in this way be used to define and implement a path from a source device to a destination device that satisfies requirements for certain traffic transported by the network.
Networks that implement multicasting, or “multicast networks,” use network resources such as routers and links differently than ordinary point-to-point flows or LSPs. Such networks may establish point-to-multipoint (P2MP) LSPs to multicast packets from a single source to multiple destinations. Using a P2MP LSP, routers of the network that are nodes of the P2MP LSP may send a single copy of a packet mapped to the P2MP LSP downstream on a given branch of the P2MP LSP. Downstream routers of the P2MP LSP to replicate the packet as needed in order to reach the downstream destinations. In this way, if the network is configured to multicast (alternatively, “broadcast”) the same data from a source to multiple destinations, the traffic need be counted only once on each branch of the tree, regardless of the number of source to destination paths rely upon the links of the branch for transporting the traffic. The network resources are used more efficiently (i.e., optimized) if the paths to different destinations for the same P2MP multicast tree use as many as possible common elements on the paths.